package com.cg.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 199.二叉树的右视图
 *
 * @program: LeetCode->LeetCode_199
 * @author: cg
 * @create: 2022-04-19 19:48
 **/
public class LeetCode_199 {

    @Test
    public void test199() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(5);

        root.right = new TreeNode(3);
        root.right.right = new TreeNode(4);
        System.out.println(rightSideView(root));
    }

    /**
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1,3,4]
     * <p>
     * 示例 2:
     * 输入: [1,null,3]
     * 输出: [1,3]
     * <p>
     * 示例 3:
     * 输入: []
     * 输出: []
     * <p>
     * 提示:
     * 二叉树的节点个数的范围是 [0,100]
     * -100 <= Node.val <= 100
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return res;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.remove();
                if (size == 1) {
                    res.add(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                size--;
            }
        }
        return res;
    }

}
